There has been explosive growth in Internet traffic due to the increased number of Internet users, various service demands from those users, the implementation of new services, such as voice-over-IP (VoIP) or streaming applications, and the development of mobile Internet. Conventional routers, which act as relaying nodes connected to sub-networks or other routers, have accomplished their roles well, in situations in which the time required to process packets, determine their destinations, and forward the packets to the destinations is usually smaller than the transmission time on network paths. More recently, however, the packet transmission capabilities of high-bandwidth network paths and the increases in Internet traffic have combined to outpace the processing capacities of conventional routers.
This has led to the development of a new generation of massively parallel, distributed architecture routers. A distributed architecture router typically comprises a large number of routing nodes that are coupled to each other via a plurality of switch fabric modules and an optional crossbar switch. Each routing node has its own routing (or forwarding) table for forwarding data packets via other routing nodes to a destination address.
When a data packet arrives in a conventional routing node, a forwarding engine in the routing node uses forwarding tables to determine the destination of the data packet. A conventional Internet Protocol (IP) router uses a dedicated forwarding table for each type of traffic, such as Internet Protocol version 4 (IPv4), Internet Protocol version 6 (IPv6) and MPLS.
Traditionally, data packets are forwarded in a router or switch by a single thread executed by a data processor. Fast hardware circuits are used to meet the throughput requirements for high-speed systems. If multiple threads are used to forward data packets, each thread typically specializes in handling a particular type of packet (i.e., each packet type is sent to a processing thread based on the packet type). This is typical of most scheduling systems. Such scheduling systems use a knowledge base that is searched according to type criteria (e.g., packet type). In either approach (i.e., single thread for all packet types or separate thread for each packet type), packet sequencing is automatically maintained because a single thread is used for each packet type. This prevents data packets from passing one another in processing.
However, if a single thread is used either to process each packet type or to process all packet types, it is not possible to achieve the throughput requirements of high-speed routers. Any splitting of the processing by packet type over multiple threads leads to a load-balancing dependence on traffic type. Eventually, normal statistical fluctuations in traffic types leads to cases where the forwarding resources (e.g., threads, microengines) for some packet types are overloaded, while forwarding resources of other packet types are idle. Thus, resources are wasted when non-optimal traffic mixtures are encountered.
Therefore, there is a need in the art for improved high-speed routers. In particular, there is a need for a high-speed router that can process data packets for different traffic types without overloading forwarding resources for some packet types, while forwarding resources for other data packet types are idle.